#-*- coding: utf-8 -*-
"""
Classe permettant le calcul formel avec des polynômes.
Par Guillaume HUYSMANS et Mathieu LECLERQ, 2013.
"""
from ListeChainee import *
from Node import *

class Polynomial(object):
    def __init__(self, s=''):
        """
        >>> print Polynomial('-3x^3+2x^2+3x+9')
        -3x^3+2x^2+3x^1+9x^0
        >>> print Polynomial('1x^3+7x^2')
        1x^3+7x^2
        >>> print Polynomial('x')
        1x^1
        >>> print Polynomial('booh')
        Traceback (most recent call last):
        ...
        ValueError: Can't parse 'booh' as a polynomial.
        """
        try:
            #Étape 1 : nettoyage
            pure = s.replace('-', '+-') #regroupement des cas
            pure = pure.replace('^', '') #caractère inutile
            pure = pure.replace('*', '') #caractère inutile
            pure = pure.replace(' ', '') #caractère inutile
            terms = pure.split('+') #sépare chaque terme
            self.cl = ListeChainee()
            #Étape 2 : on ajoute chaque terme
            for t in terms:
                if t!='':
                    #si le terme n'est pas vide, on travaille dessus
                    d = t.split('x')
                    n = Polynomial.conv(d[0]) if d[0]!='' else 1
                    if 'x' in t:
                        #si l'exp existe, on l'utilise, sinon 1
                        e = int(d[1]) if d[1]!='' else 1 
                    else:
                        e = 0 #pas d'exposant
                    #seulement si y'a un coefficient... sinon inutile
                    if n!=0:
                        self._addTerm(n, e)
        except:
            raise ValueError("Can't parse %s as a polynomial." % repr(s))

    def __copy__(self):
        """
        >>> x = Polynomial('3x^2')
        >>> y = copy(x)
        >>> x.cl.head.data = (1, 2)
        >>> print x
        1x^2
        >>> print y
        3x^2
        """
        #On conserve l'ordre, il est supposé être correct.
        ret = Polynomial()
        p = self.cl.head
        while p!=None:
            ret.cl.insertEnd(p.data)
            p = p.next
        return ret

    def _addTerm(self, n, e, rpl=False):
        """
        Insère au bon endroit un terme nx^e dans la liste interne
        S'il existe déjà, il sera RemPLacé ou incrémenté de/par n.
        >>> print Polynomial('1x^1+7x^0+1x^1')
        2x^1+7x^0
        >>> print Polynomial('1x^2+7x^0+1x^1')
        1x^2+1x^1+7x^0
        """
        p = self.cl.head
        prev = None
        while p!=None:
            if p.data[1] == e:
                v = n if rpl else n+p.data[0]
                if v==0:
                    #il ne sert plus à rien !
                    #supprimons-le...
                    if prev==None:
                        self.cl.head = p.next
                    else:
                        prev.next = p.next
                    self.cl.size -= 1
                else:
                    #petit tour de passe-passe : un tuple est immuable !
                    #on doit donc l'écraser complètement
                    tmp = (v, e)
                    p.data = tmp 
                return
            elif p.data[1] < e:
                if prev==None:
                    #c'est le premier...
                    nv = Node((n, e), self.cl.head)
                    self.cl.head = nv
                else:
                    nv = Node((n, e), p)
                    prev.next = nv
                self.cl.size += 1
                return
            prev = p #on retient le précédent pour pouvoir intercaler
            p = p.next
        #pas encore trouvé, on ajoute à la fin
        self.cl.insertEnd((n, e))

    def __setitem__(self, i, v):
        """
        >>> x = Polynomial('2x^2')
        >>> x[0] = 1
        >>> x[2] = 3
        >>> print x
        3x^2+1x^0
        """
        self._addTerm(v, i, True)

    def __getitem__(self, i):
        """
        >>> Polynomial('2x^2')[0]
        0
        >>> Polynomial('2x^2')[2]
        2
        >>> Polynomial('4x^3+2x+5')[2]
        0
        """
        p = self.cl.head
        while p!=None:
            if p.data[1]==i:
                return p.data[0]
            elif p.data[1]<i:
                #comme la liste est triée, si on l'a "dépassé",
                #il ne risque pas d'être plus loin !
                return 0
            p = p.next
        return 0 #pas trouvé !

    def __delitem__(self, i):
        """
        >>> x = Polynomial('2x^2+3x+5')
        >>> del x[2]
        >>> print x
        3x^1+5x^0
        """
        self._addTerm(0, i, True)

    def __str__(self):
        """
        >>> print Polynomial('-3x^3+2x^2+3x+9')
        -3x^3+2x^2+3x^1+9x^0
        >>> print Polynomial('')
        0
        """
        nd = self.cl.head
        if nd==None:
            return '0'
        else:
            s = ""
            while nd!=None:
                s += str(nd.data[0]) + 'x^' + str(nd.data[1]) + '+'
                nd = nd.next
            return s[:-1] #on retire le dernier +

    def __repr__(self):
        """
        >>> Polynomial('-3x^3+2x^2+3x+9')
        Polynomial("-3x^3+2x^2+3x^1+9x^0")
        """
        return 'Polynomial("' + str(self) + '")'

    def __len__(self):
        return len(self.cl)

    def __add__(self, other):
        """
        >>> print Polynomial('2x^2+3x') + Polynomial('2x^3+2x^2+3x')
        2x^3+4x^2+6x^1
        """
        if not isinstance(other, Polynomial):
            raise NotImplemented("Polynomial doesn't support other types")
        cp = copy(self)
        p = other.cl.head
        while p!=None:
            cp._addTerm(*p.data)
            p = p.next
        return cp

    def __sub__(self, other):
        """
        >>> print Polynomial('2x^2+3x') - Polynomial('2x^3+2x^2+3x')
        -2x^3
        """
        if not isinstance(other, Polynomial):
            raise NotImplemented("Polynomial doesn't support other types")
        cp = copy(self)
        p = other.cl.head
        while p!=None:
            cp._addTerm(-p.data[0], p.data[1])
            p = p.next
        return cp

    def __mul__(self, other):
        """
        >>> print Polynomial('2x^2') * 2
        4x^2
        >>> print Polynomial('2x^2') * Polynomial('x')
        2x^3
        >>> print Polynomial('x+1') * Polynomial('x+1')
        1x^2+2x^1+1x^0
        >>> print Polynomial('3x^2+2') * Polynomial('2x^3+1')
        6x^5+4x^3+3x^2+2x^0
        """
        if isinstance(other, Polynomial):
            acc = Polynomial() #polynome vide
            p = other.cl.head
            while p!=None:
                tmp = self*p.data[0] #mult. par le facteur réel
                #ajustement des exposants
                p2 = tmp.cl.head
                while p2!=None:
                    nv = (p2.data[0], p2.data[1]+p.data[1])
                    p2.data = nv
                    p2 = p2.next
                acc += tmp #accumulation
                p = p.next #facteur suivant
            return acc
        else:
            cp = copy(self)
            p = cp.cl.head
            while p!=None:
                tmp = (p.data[0] * other, p.data[1])
                p.data = tmp
                p = p.next
            return cp

    def __div__(self, other):
        """
        >>> print Polynomial('4x^2+8x+16')/2
        2.0x^2+4.0x^1+8.0x^0
        >>> print Polynomial('7x^2+9x+2')/Polynomial('x+1')
        7x^1+2x^0
        >>> print Polynomial('x+2')/Polynomial('x+2')
        1x^0
        >>> print Polynomial('x')/Polynomial('x+2')
        (Polynomial("1x^0"), -2)
        >>> print Polynomial('1')/Polynomial('x')
        (Polynomial("0"), 1)
        >>> print Polynomial('0')/Polynomial('x-1')
        0
        """
        #TODO la complexité pourrait être améliorée mais le code deviendrait VRAIMENT trop compliqué.
        #C'est déjà pas évident comme ça, mais s'il fallait ajouter dedans une boucle pour considérer les trous...
        if isinstance(other, Polynomial):
            if len(self)==0:
                #cas tordu (P0/P)
                return Polynomial('')
            elif other.cl.head.data[1]==1 and other.cl.head.data[0]==1:
                deg = self.cl.head.data[1]
                if deg==0:
                    #cas tordu (P1/PX)
                    return (Polynomial(''), self.cl.head.data[0])
                else:
                    if other.cl.head.next:
                        div = -other.cl.head.next.data[0]
                    else:
                        div = 0 #par défaut...
                    acc = self.cl.head.data[0]
                    nw = Polynomial('')
                    #on descend toujours le premier. Pas besoin de vérifier sa valeur,
                    #il ne peut pas être nul (sinon il ne serait pas là)
                    nw.cl.insertEnd((acc, deg-1)) 
                    while deg>0:
                        deg -= 1 #on descend d'un degré (graphiquement, décalage)
                        acc = self[deg] + div*acc #on fait le calcul
                        if deg>0:
                            #c'est un vrai terme, on l'ajoute au résultat
                            #Attention, on ne l'ajoute que s'il sert à quelque chose
                            if acc!=0:
                                nw.cl.insertEnd((acc, deg-1))
                        else:
                            #c'est un reste
                            if acc==0:
                                #il est nul, ça tombe bien, on renvoit un polynôme
                                return nw
                            else:
                                #il est non nul, on renvoit un tuple pour ne pas perdre l'info
                                return nw, acc
            else:
                #FIXME il existe peut-être une version généralisée de la division par Horner...
                raise NotImplemented("Horner division doesn't support division by "+str(other))
        else:
            return self * (1/float(other))

    def diff(self):
        """
        Dérive le polynôme.

        >>> x = Polynomial('2x^3+3x^2+10')
        >>> x.diff()
        >>> print x
        6x^2+6x^1
        >>> x.diff()
        >>> print x
        12x^1+6x^0
        >>> x.diff()
        >>> print x
        12x^0
        >>> x.diff()
        >>> print x
        0
        """
        p = self.cl.head
        prev = None #précédent
        prev2 = None #précédent précédent...
        while p!=None:
            tmp = (p.data[0] * p.data[1], p.data[1]-1)
            p.data = tmp #remplacement !
            prev2 = prev
            prev = p
            p = p.next
        #maintenant, p=None, prev=dernier, prev2=avant-dernier
        if self.cl.head!=None:
            #liste non vide. Testons l'exposant du dernier terme...
            if tmp[1] < 0:
                #il est négatif : il faut l'éliminer ! Mais comment ?
                if prev2==None:
                    #c'est le premier & dernier). On n'a qu'à vider la liste !
                    self.cl.clear()
                else:
                    #c'est "seulement" le dernier... ne perdons pas de temps :
                    #avec removeTail(), on a déjà ue réf vers son précédent.
                    prev2.next = None
                    self.cl.tail = prev2

    def deriv(self):
        """
        Calcule la dérivée du polynôme et le renvoit directement.

        Terme indépendant
        >>> x = Polynomial('2x^3+3x^2+10')
        >>> print x.deriv()
        6x^2+6x^1

        Terme indépendant seul
        >>> x = Polynomial('10')
        >>> print x.deriv()
        0

        x devient constant
        >>> x = Polynomial('x')
        >>> print x.deriv()
        1x^0
        """
        nw = copy(self)
        nw.diff()
        return nw

    def eval(self, x):
        """Injecte x dans le polynôme et retourne le résultat."""
        acc = 0
        p = self.cl.head
        while p!=None:
            acc += p.data[0] * x**p.data[1]
            p = p.next
        return acc

    @staticmethod
    def conv(n):
        """
        Convertit une chaine représentant un nombre en int ou float.
        On aurait pu passer directement par float(), mais autant éviter le gaspillage...
        """
        r = float(n)
        if r-int(r)==0:
            #float inutile car entier
            r = int(r)
        return r

if __name__=='__main__':
    import doctest
    doctest.testmod()
